/*
 * @lc app=leetcode.cn id=282 lang=golang
 *
 * [282] 给表达式添加运算符
 */

// @lc code=start
import (
	"strconv"
	"strings"
)

func addOperators(num string, target int) []string {
	c := []rune{'+', '-', '*', ' '}
	res := make([]string, 0)
	n := len(num)
	rnums := []rune(num)
	tmp := make([]rune, 2*n-1)
	for i, j := 0, 0; j < n; i, j = i+2, j+1 {
		tmp[i] = rnums[j]
	}
	dfs(c, 1, &tmp, target, &res)

	return res

}

func dfs(c []rune, index int, tmp *[]rune, target int, res *[]string) {
	if index >= len(*tmp) {
		var trans strings.Builder
		for _, v := range *tmp {
			if v == ' ' {
				continue
			}
			trans.WriteRune(v)
		}
		ss := toPolanString(trans.String())
		for _, v := range ss {
			if strings.HasPrefix(v, "0") && len(v) > 1 {
				return
			}
		}
		num := getResult(ss)
		if num == target {
			*res = append(*res, trans.String())
		}
		return
	}
	for _, v := range c {
		(*tmp)[index] = v
		if (*tmp)[index+1] == 0 && v == '/' {
			continue
		}
		dfs(c, index+2, tmp, target, res)
	}
}

// 计算逆波兰式结果，即表达式结果
func getResult(ss []string) int {
	n := len(ss)
	stack := make([]int, 0, n)
	for i := 0; i < n; i++ {
		if ss[i] != "+" && ss[i] != "-" && ss[i] != "*" && ss[i] != "/" {
			// stack = append(stack, )
			v, _ := strconv.Atoi(ss[i])
			stack = append(stack, v)
		} else {
			num := cacl(stack[len(stack)-2], stack[len(stack)-1], ss[i])
			stack = stack[:len(stack)-2]
			stack = append(stack, num)
		}
	}
	return stack[0]
}
func cacl(a, b int, c string) int {
	switch c {
	case "+":
		return a + b
	case "-":
		return a - b
	case "*":
		return a * b
	case "/":
		if b == 0 {
			return -1
		}
		return a / b
	}
	return 0
}

// 表达式后缀表达式，逆波兰式
func toPolanString(s string) []string {
	n := len(s)
	stack := make([]byte, 0, n)
	res := make([]string, 0, n)
	prior := make(map[byte]int)
	prior['+'] = 1
	prior['-'] = 1
	prior['*'] = 2
	prior['/'] = 2
	for i := 0; i < n; i++ {
		if s[i] == ' ' {
			continue
		}
		if s[i] >= '0' && s[i] <= '9' {
			var tmp strings.Builder
			for ; i < n; i++ {
				if s[i] >= '0' && s[i] <= '9' {
					tmp.WriteByte(s[i])
				} else {
					break
				}
			}
			res = append(res, tmp.String())
			i--
		} else {
			if len(stack) == 0 {
				stack = append(stack, s[i])
				continue
			}
			v1, _ := prior[s[i]]
			v2, _ := prior[stack[len(stack)-1]]
			for v1 <= v2 {
				if len(stack) <= 0 || stack[len(stack)-1] == '(' {
					break
				}
				res = append(res, string(stack[len(stack)-1]))
				stack = stack[:len(stack)-1]
				if len(stack) <= 0 || stack[len(stack)-1] == '(' {
					break
				}
				v2, _ = prior[stack[len(stack)-1]]
			}
			stack = append(stack, s[i])

		}
	}
	for len(stack) > 0 {
		res = append(res, string(stack[len(stack)-1]))
		stack = stack[:len(stack)-1]
	}
	return res
}

// @lc code=end
